In the art of information storage and transmission, it is known that the representation of such data often contains redundant information. By way of explanation it is necessary to know that information in such data storage or data transmission systems is usually represented by some number of bits as determined by the given character scheme employed by the system. In such a scheme a fixed number of bits is used to represent every possible character in the set.
By way of example, if the character size is eight bits in length then up to 256 characters may be represented by these eight bits. While this provides a standard method of character representation, it can greatly increase the size of the data stored or transmitted as each character always requires the full character size (e.g. eight bits).
In such data transmission or data storage systems, it is therefore valuable to have a method of altering the size of the representation of each character such that frequently used characters consume less of the available resource in use. Such a process is often referred to as "data compression".
Data compression increases the density of the data stored while retaining all of the original information. Compressing the data permits it to be stored in smaller amounts of storage area. It also permits the data to be transmitted over a communication connection in less time. Employing such compression provides significant reduction in the cost of storing or transmitting data.
A well known method of performing data compression is the use of variable length encoding method. A well known such method is referred to as a Huffman code. A Huffman code converts data of a uniform character length into encoded data of variable length. The construction of Huffman codes is further described in an article by David Huffman entitled "A Method For The Construction of Minimum Redundancy Codes" in the proceedings of the I.R.E., Volume 40, pages 1098 to 1101, 1952. Such a method is often preferred over other variable length codes due to the straight forward nature of the construction of the encoded data and the optimum expected average length of the encoded characters.
While variable length encoded data is useful for reducing the cost of performing transmission or storage of data, the encoded data cannot be used by the destination system in such a form. As such encoded data must eventually be decoded back to its fixed length format. As such, there is a need for a convenient, efficient and practical way to decode variable length encoded data. Ideally, such a method could be employed in a conventional data processing system.
There is also a need to perform such decoding in the most rapid manner possible since the speed of such decoding effects the efficiency of the entire system employing the encoded data. For example, it is desireable that a fax machine decode variable length encoded data it receives in a rapid fashion to increase the amount of data the machine can process.
Variable length encoded data frequently requires that the encoded information be processed one bit at a time. Since the length of the data is variable, it is uncertain how many bits comprise a given character. One method of decoding begins with the first bit and does a comparison to determine if that length of data corresponds to a character in the encoded set. If not, successive single bits from the encoded data are concatenated to the first bit until a unique character is decoded within the system.